CSE 311: Foundations of Computing I

CSE 311: Homework 1 Part 2

Due: Friday, April 10th by 6:00 PM

Instructions

Write up carefully argued solutions to the following problems. Each solution should be clear enough that it can explain (to someone who does not already understand the answer) why it works. However, you may use results from lecture, the reference sheets, and previous homework without proof.

You are required to submit your own solutions. You are allowed to discuss the homework with other students. However, the write up must clearly be your own, and moreover, you must be able to explain your solution at any time. We reserve ourselves the right to ask you to explain your work at any time in the course of this class.

You have a total of three late days during the quarter, but you can only use one late day on any one homework, giving an additional day on both parts. Please plan ahead.

Submit your solution via Gradescope. In particular:

  • Each numbered task should be solved on its own page (or pages). Do not write your name on the individual pages. (Gradescope will handle that.)

  • When you upload your pages, make sure each one is properly rotated. If not, you can use the Gradescope controls to turn them to the proper orientation.

  • Follow the Gradescope prompt to link tasks to pages.

  • You are not required to typeset your solution, but your submission must be legible. It is your responsibility to make sure solutions are readable — we will not grade unreadable write-ups.

Task 1 – With a Fine-Truth Comb

For each of the following pairs of propositions, use truth tables to determine whether they are equivalent.

Include the full truth table and state whether they are equivalent. (In principle, only one row is needed to show non-equivalence, but please turn in the entire table so that we can give partial credit in case of errors.) Your truth table must include columns for all subformulas.

  1. P↔QP \leftrightarrow Q vs. ¬P↔(P∧Q)\neg P \leftrightarrow (P \wedge Q)

  2. (P↔Q)→R(P \leftrightarrow Q) \to R vs. (P∨R)∧(Q→R)(P \vee R) \wedge (Q \to R)

Task 2 – Too Cool For Rule

Prove the following assertions using a sequence of logical equivalences such as Absorption, Associativity, Commutativity, Contrapositive, De Morgan, Distributivity, Double Negation, Idempotency, Identity, Law of Implication, and Negation.

Hints: For equivalences where one side is much longer than the other, a good heuristic is to start with the longer side and try to apply the rules that will shorten it. In some cases, it may work better to work to shorten both sides to the same expression and then combine those two sequences into one.

  1. (¬P∨Q)∧(¬P∧Q)≡¬P∧Q(\neg P \vee Q) \wedge (\neg P \wedge Q) \equiv \neg P \wedge Q (Hint: It is not necessary to use Distributivity here.)

  2. (P→¬Q)∧(¬P→¬Q)≡¬Q(P \to \neg Q) \wedge (\neg P \to \neg Q) \equiv \neg Q

  3. (P∨Q→R)→Q≡(¬P→Q)∧(R→Q)(P \vee Q \to R) \to Q \equiv (\neg P \to Q) \wedge (R \to Q)

Task 3 – Truth or Feb?

In this task, let the domain of discourse be the calendar months: Jan, Feb, Mar, ..., Dec. The following parts use the predicates HasThirtyDays, HasEvenDays, and IsFebruary, defined as follows: 𝖧𝖺𝗌𝖳𝗁𝗂𝗋𝗍𝗒𝖣𝖺𝗒𝗌(x):=“x has exactly 30 days”𝖧𝖺𝗌𝖤𝗏𝖾𝗇𝖣𝖺𝗒𝗌(x):=“x has an even number of days”𝖨𝗌𝖥𝖾𝖻𝗋𝗎𝖺𝗋𝗒(x):=“x is February”\begin{aligned} \mathop{\mathrm{\textsf{HasThirtyDays}}}(x) &:= \text{``$x$ has exactly 30 days''} \\ \mathop{\mathrm{\textsf{HasEvenDays}}}(x) &:= \text{``$x$ has an even number of days''} \\ \mathop{\mathrm{\textsf{IsFebruary}}}(x) &:= \text{``$x$ is February''} \end{aligned} For this problem, you should make your English translations sound natural (see slide 177 of Topic 1). When stating whether a proposition is true or false, you do not need to justify your answer.

  1. Let the domain of discourse be all calendar months.

    1. Translate the proposition directly into English. Then, state whether the proposition is true or false.

      ∀x(𝖧𝖺𝗌𝖤𝗏𝖾𝗇𝖣𝖺𝗒𝗌(x)→𝖧𝖺𝗌𝖳𝗁𝗂𝗋𝗍𝗒𝖣𝖺𝗒𝗌(x))\forall x\,(\mathop{\mathrm{\textsf{HasEvenDays}}}(x) \to \mathop{\mathrm{\textsf{HasThirtyDays}}}(x))

    2. Translate the proposition directly into English. Then, state whether the proposition is true or false.

      ∀x((𝖧𝖺𝗌𝖤𝗏𝖾𝗇𝖣𝖺𝗒𝗌(x)∧¬𝖨𝗌𝖥𝖾𝖻𝗋𝗎𝖺𝗋𝗒(x))→𝖧𝖺𝗌𝖳𝗁𝗂𝗋𝗍𝗒𝖣𝖺𝗒𝗌(x))\forall x\, ((\mathop{\mathrm{\textsf{HasEvenDays}}}(x) \land \neg \mathop{\mathrm{\textsf{IsFebruary}}}(x)) \to \mathop{\mathrm{\textsf{HasThirtyDays}}}(x))

    3. Translate the proposition directly into English. Then, state whether the proposition is true or false.

      (∀x(𝖧𝖺𝗌𝖤𝗏𝖾𝗇𝖣𝖺𝗒𝗌(x)∧¬𝖨𝗌𝖥𝖾𝖻𝗋𝗎𝖺𝗋𝗒(x)))→(∀x𝖧𝖺𝗌𝖳𝗁𝗂𝗋𝗍𝗒𝖣𝖺𝗒𝗌(x))(\forall x\,(\mathop{\mathrm{\textsf{HasEvenDays}}}(x) \land \neg \mathop{\mathrm{\textsf{IsFebruary}}}(x))) \to (\forall x\,\mathop{\mathrm{\textsf{HasThirtyDays}}}(x))

  2. Now, let the domain of discourse be just the winter months (Dec, Jan, Feb). For each of the parts (i–iii) from part (a), state whether the claim would be true with this new domain of discourse.

  3. Let the domain of discourse again be all calendar months. Translate the following English sentences into propositions in first-order logic, using the predicates defined above.

    1. No month with thirty days is February.

    2. There is a month that does not have an even number of days and is not February.

    3. February is the only month with an even number of days that does not have thirty days.

Task 4 – Optional Practice Problems (Extra Credit)

The following problems are optional and do not need to be submitted. However, you may submit solutions and receive a small amount of extra credit for any 5 (of the 8) subparts, graded solely on completion.

  1. Define a set of four atomic propositions. Then, use them to translate the following sentences into propositional logic.

    1. The flight is delayed if there is a storm or if the aircraft does not have both fuel and clearance.

    2. The flight does not have clearance only if it is delayed and there is a storm.

  2. Shane practices a personal ritual every day to decide whether he will drink a ginger ale. He flips a coin 4 times, and assigns values of 1 (heads) or 0 (tails) to variables aa, bb, cc, and dd based on the results of the flips, in that order. Shane then applies a secret boolean function GG to those variables, and drinks a ginger ale if and only if G(a,b,c,d)=1G(a, b, c, d) = 1.

    Ilya wants to figure out the secret function GG. After extensive observation, he has recorded a truth table for GG, shown below. Help Ilya reconstruct the function!

    aa bb cc dd G(a,b,c,d)G(a, b, c, d)
    1 1 1 1 1
    1 1 1 0 0
    1 1 0 1 1
    1 1 0 0 1
    1 0 1 1 1
    1 0 1 0 0
    1 0 0 1 1
    1 0 0 0 1
    0 1 1 1 1
    0 1 1 0 0
    0 1 0 1 1
    0 1 0 0 0
    0 0 1 1 1
    0 0 1 0 0
    0 0 0 1 1
    0 0 0 0 0

    1. Write a Boolean algebra expression for GG in canonical CNF form.

    2. Use equivalences of Propositional Logic to simplify your expression from (a) down to an expression that includes only 3 gates (each of which is either AND, OR, or NOT).

      You should format your work like an equivalence chain with one expression per line and with the name of the identity applied to produce that line written next to it. However, since we are using Boolean algebra notation, which does not include unnecessary parentheses, you do not need to include lines that apply Associativity, Commutativity, or Identity (you may still cite them for clarity if desired).

  3. Write truth tables for the following propositions.

    1. p∨(q→¬p)p\lor (q\to\neg p)

    2. (p→q)→(r→p)(p\to q)\to(r\to p)

  4. Prove the following equivalences using an equivalence chain.

    1. p∨(q→¬p)≡𝖳p\lor (q\to\neg p) \equiv \textsf{T}.

    2. (p→q)∧(q→r)≡(p→q)∧(q→r)∧(p→r)(p\to q)\land(q\to r)\equiv(p\to q)\land(q\to r)\land(p\to r). Hint: work from both sides.